package  main.java.leetcode.editor.cn;
//2022-06-01 20:45:14
//你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能
//折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。 
//
// 如果你能使这个正方形，则返回 true ，否则返回 false 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: matchsticks = [1,1,2,2,2]
//输出: true
//解释: 能拼成一个边长为2的正方形，每边两根火柴。
// 
//
// 示例 2: 
//
// 
//输入: matchsticks = [3,3,3,3,4]
//输出: false
//解释: 不能用所有火柴拼成一个正方形。
// 
//
// 
//
// 提示: 
//
//
// 1 <= matchsticks.length <= 15 
// 1 <= matchsticks[i] <= 10⁸ 
// 
// Related Topics 位运算 数组 动态规划 回溯 状态压缩 👍 367 👎 0

class MatchsticksToSquare {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new MatchsticksToSquare().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for(int num : matchsticks){
            sum += num;
        }
        if(sum%4 != 0 || sum == 0){
            return false;
        }

        return backtrack(matchsticks, matchsticks.length-1, sum/4,new int[4]);

    }

    public boolean backtrack(int[] arr,int index,int target,int[] size){

        if(index == -1){
            if(size[0]==size[1] && size[1]==size[2] && size[2]==size[3]){
                return true;
            }
            return false;
        }

        for(int i = 0;i<size.length;i++){
            //(i>0 && size[i]==size[i-1])保证和前一个边相等
            if(size[i]+arr[index]>target || (i>0 && size[i]==size[i-1])){
                continue;
            }
            size[i] += arr[index];
            //只有最后一次必然会运行true
            if(backtrack(arr,index-1,target,size)){
                return true;
            }

            size[i] -= arr[index];
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
